// 树结构的定义
function TreeNode(x) {
  this.val = x;
  this.left = null;
  this.right = null;
}
// ES6 class写法二叉树
class BinaryTree {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// ----------------------------------------------------------------
// 树的前序遍历 - 递归遍历
function preOrderRe(root) {
  let res = [];
  function preOrderFunc(root) {
    if (root) {
      res.push(root.val);
      preOrderFunc(root.left);
      preOrderFunc(root.right);
    }
    return null;
  }
  preOrderFunc(root);
  return res.toString();
}
// 树的前序遍历 - 非递归遍历
function preOrder(root) {
  if (!root) return null;
  let nodes = [];
  let res = [];
  // 将根节点存入数组
  nodes.push(root);
  while (nodes.length) {
    // 数组pop一个元素 pop方法会返回弹出的元素
    let node = nodes.pop();
    // 层序顺序写入res
    res.push(node.val);
    // 先把弹出元素的右子节点推入数组中
    if (node.right) {
      nodes.push(node.right);
    }
    // 再把左节点推入数组
    if (node.left) {
      nodes.push(node.left);
    }
  }
  return res.toString();
}
// ----------------------------------------------------------------
// 树的中序遍历 - 递归遍历
function midOrderRe(root) {
  let res = [];
  function midOrderFunc(root) {
    if (root) {
      midOrderFunc(root.left);
      res.push(root.val);
      midOrderFunc(root.right);
    }
    return null;
  }
  midOrderFunc(root);
  return res.toString();
}
// 树的中序遍历 - 非递归遍历
function midOrder(root) {
  let nodes = [];
  let res = [];
  while (root || nodes.length) {
    if (root) {
      nodes.push(root);
      root = root.left;
    } else {
      let node = nodes.pop();
      res.push(node.val);
      root = node.right;
    }
  }
  return res.toString();
}
// ----------------------------------------------------------------
// 树的后序遍历 - 递归遍历
function backOrderRe(root) {
  let res = [];
  function backOrderFunc(root) {
    if (root) {
      backOrderFunc(root.left);
      backOrderFunc(root.right);
      res.push(root.val);
    }
    return null;
  }
  backOrderFunc(root);
  return res.toString();
}
// 树的后序遍历 - 非递归遍历
function backOrder(root) {
  if (!root) return null;
  let nodes = [];
  let res = [];
  nodes.push(root);
  while (nodes.length) {
    let node = nodes.pop();
    res.unshift(node.val);
    node.left && nodes.push(node.left);
    node.right && nodes.push(node.right);
  }
  return res.toString();
}
// ----------------------------------------------------------------
// 树的层序遍历 - 非递归遍历
function levelOrder(root) {
  // write code here
  if (!root) return [];
  let res = [];
  // 这里nodes使用队列的方式
  let nodes = [];
  nodes.push(root);
  while (nodes.length) {
    const len = nodes.length;
    let tmp = [];
    for (let i = 0; i < len; i++) {
      // 这里是使用队列的方式存储每层的内容
      let node = nodes.shift();
      tmp.push(node.val);
      if (node.left) {
        nodes.push(node.left);
      }
      if (node.right) {
        nodes.push(node.right);
      }
    }
    res.push(tmp);
  }
  return res.toString();
}

// --------------------------测试demo--------------------------------------

//        1
//     /      \
//    2        3
//  /   \     /   \
// 4     5   6     7
// root 结构如上
let root = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null,
    },
    right: {
      val: 5,
      left: null,
      right: null,
    },
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: {
      val: 7,
      left: null,
      right: null,
    },
  },
};

// 测试前序遍历递归方法
console.log("----------前序遍历------------");
console.log(preOrder(root)); // [1, 2, 4, 5, 3, 6, 7]
console.log(preOrderRe(root)); // [1, 2, 4, 5, 3, 6, 7]
console.log("----------中序遍历------------");
console.log(midOrder(root)); // [4, 2, 5, 1, 6, 3, 7]
console.log(midOrderRe(root)); // [4, 2, 5, 1, 6, 3, 7]
console.log("----------后序遍历------------");
console.log(backOrder(root)); // [4, 5, 2, 6, 7, 3, 1]
console.log(backOrderRe(root)); // [4, 5, 2, 6, 7, 3, 1]
console.log("----------层序遍历------------");
console.log(levelOrder(root)); // [ [ 1 ], [ 2, 3 ], [ 4, 5, 6, 7 ] ]

// ----------树的demo-----------
//  前序遍历
const preTree = (root) => {
  if (root) {
    console.log(root.val);
    preTree(root.left);
    preTree(root.right);
  }
  return null;
};
//  中序遍历
const midTree = (root) => {
  if (root) {
    preTree(root.left);
    console.log(root.val);
    preTree(root.right);
  }
  return null;
};
//  后序遍历
const backTree = (root) => {
  if (root) {
    preTree(root.left);
    preTree(root.right);
    console.log(root.val);
  }
  return null;
};
// TreeDemo1 一个二叉树实例
const TreeDemo1 = new BinaryTree(1);
TreeDemo1.left = new BinaryTree(2);
TreeDemo1.right = new BinaryTree(3);
TreeDemo1.left.left = new BinaryTree(4);
TreeDemo1.left.right = new BinaryTree(5);
TreeDemo1.right.left = new BinaryTree(6);
TreeDemo1.right.right = new BinaryTree(7);
// TreeDemo1的结构为如下
//        1
//      /   \
//     2     3
//    / \   / \
//   4   5  6  7
console.log("数的demo");
console.log(TreeDemo1);
console.log("前序遍历结果");
preTree(TreeDemo1);
console.log("中序遍历结果");
midTree(TreeDemo1);
console.log("后序遍历结果");
backTree(TreeDemo1);
